\section{Introduction}
 
%\begin{enumerate}
%\item In this paper, we propose a unsupervised approach to leverage the semantics-based and similarity-based ways for addressing the problem of instance matching on the Semantic Web.
%\item Describe the problem in the context of the semantic web, because it is where lies the strength of SERIMI.
% \item Describe as contribution:
% \item SERIMI leverage the semantic definitions owl:IFP from statistics computed on-the-fly in the data, and uses it to infer same:As relations between instances.
% \item SERIMI proposes a kernel that is does not require the source and target datasets to overlap beside a common key that they may share. SERIMI is not limit to this and can make use of direct comparison when the source and target data indeed overlap.
 %\item SERIMI proposes a grouping of the source instances that gives the maximum information hint about the target instances.
 %\item We define a measure of data complexity that indicates how complex a dataset is and it is used by SERIMI to improve the matching process.This data complexity measure is used to select the necessary and sufficient combination of attributes used in the matching process.
%\end{enumerate}


%\textit{The Semantic Web} is an ongoing initiative by \textit{W3C} to promote standards and methods for data integration at web scale. 
A large amount of datasets have been made available on the Web as a result of initiatives such as Linking Open Data. As a general graph-structured data model, RDF is widely used 
%for data representation and exchange, 
especially for publishing Web datasets. In RDF, an entity, also called an instance, is represented via $\langle subject,$ $predicate, object \rangle$ statements (called \emph{triples}). Predicates and objects capture \textit{attributes} and \textit{values} of an instance, respectively (terms that are used interchangeably here). A RDF data example is shown in Table 1. 
%, which comprises several instance descriptions. 

%Many ontologies are available to represent these RDF triples, they define common predicates, classes and the semantic of the data, so that machines can reasoning over the data. 
Besides RDF, OWL is another standard language for knowledge representation, especially for capturing the ``same-as'' semantics of instances. Using  \verb+owl:sameas+, data providers can make explicit that two distinct URIs actually refer to the same real world entity. 
%One major goal of the Open Linking Data initiative is to establish these same-as links to connect and combine instance descriptions that reside in different datasets. 
The task of establishing these same-as links is known under various names such as entity resolution and \emph{instance matching}. 
% is clearly essential to the quality and growth of Web data. Generally, it is relevant in any data integration scenario in which datasets vary in the syntactic representation of entities. 
%On the Web, solutions can be distinguished into two types. 

There are \textit{semantic-driven approaches} that uses specific OWL semantics, such as explicit \verb+owl:sameas+ statements, to allow the same-as relations to be inferred via logical reasoning. 
%Clearly, this type of approaches is only effective when datasets are represented in OWL and capture the semantics necessary for reasoning. 
Complementary to this, there are \textit{data-driven approaches} that derive same-as relations mainly based on attribute values of instances. Namely, two instances are considered the same when they have many attribute values in common. 
%For instance, \verb+nyt:5962+ is recognized as being the same as \verb+db:BelmontCalifornia+ because they both have 'Belmont' as \verb+rdfs:label+. 
While they vary with respect to the selection and weighting of features, all data-driven approaches are built upon the same paradigm of \textit{direct matching}, namely they directly compare the instance representations. 
%By direct matching two instance representations, they refer to the same real word entity if their similarities exceed a threshold. 
Hence, they produce only high quality results when there is sufficient overlap between instance representations. Overlaps however, might be small in heterogeneous datasets.

 In this scenario of \emph{instance matching across heterogeneous datasets}, direct matching alone often cannot deliver high quality results. For instance, in Table 1, \verb+nyt:5962+ and \verb+db:Belmont_France+ shares the same \verb+rdfs:label+. However, \verb+rdfs:label+ is the only attribute in which overlaps can be found. 
% for instances in these datasets. 
 This overlap alone is not sufficient to determine whether they are the same (and \verb+nyt:5962+ and \verb+db:Belmont_+\verb+France+ are not the same). 

\begin{table}[t]
\centering
\caption{Instance represented as RDF triples.}
%\scriptsize\tt
\scriptsize
%\small
\begin{tabular}{|l|l|l|}
\hline 
nyt:2223 & rdfs:label & 'San Francisco' \\
nyt:5962 & rdfs:label & 'Belmont' \\
nyt:5962 & geo:lat & '37.52' \\
nyt:5555 & rdfs:label & 'San Jose' \\
nyt:4232 & nyt:prefLabel & 'Paris' \\
 

geo:525233 & rdfs:label & 'Belmont' \\ 
  & in:country & geo:887884 \\ 
 & geo:lat & '37.52' \\
 
    db:Usa & owl:sameas & geo:887884 \\ 
  db:Paris & rdfs:label & 'Paris' \\ 
  & db:country & db:France \\
db:Belmont\_France & rdfs:label & 'Belmont' \\ 
  & db:country & db:France \\  
db:Belmont\_California & rdfs:label & 'Belmont' \\ 
  & db:country & db:Usa \\  
 
db:San\_Francisco & rdfs:label & 'San Francisco' \\ 
  & db:country & db:Usa \\ 
    & db:locatedIn & db:California \\ 
  db:San\_Jose\_California & rdfs:label & 'San Jose' \\ 
    & db:locatedIn & db:California \\ 
    db:San\_Jose\_Costa\_Rica & rdfs:label & 'San Jose' \\ 
  & db:country & db:Costa\_Rica \\ 
  \hline 
\end{tabular} 
\end{table}


%Some authors\cite{DBLP:conf/www/HuCQ11} propose to combine the semantic-driven and data-driven approaches to obtain the best of both worlds. For instance, in Table 1, we could find the match for \textit{geo:525233} is \textit{db:Belmont\_California} by direct matching their \textit{rdfs:label} and reinforce the match by inferring that \textit{db:Usa} is the same than \textit{geo:887884}. 
%
%Although these approaches are feasible, the question about why and when they work, still remains. Due heterogeneous nature of the Semantic Web data, which is incomplete, noisy and diverse, an import question for instance matching is:  What characteristics the data must have to the data-driven or semantic-driven approach work with its highest accuracy? Is there any other data characteristic that can be exploited to improve the accuracy of those methods?

\textbf{Contributions.} We provide a (1) \emph{detailed analysis} of many datasets and matching tasks investigated in the OAEI 2010 and 2011 \cite{DBLP:conf/semweb/EuzenatFHHMNRSSSST11} instance matching benchmarks. We show that tasks greatly vary in their complexity. There are difficult tasks with a small overlap  between datasets that cannot be effectively solved using state-of-the-art direct matching approaches. 
%It is based on the coverage and discriminative power of the instances' predicates. This complex measure is used to select the necessary and sufficient combination of predicates so that the overlapping of information between instance representations is maximized. Consequently producing the highest matching accuracy.
Aiming at these tasks, we propose to use direct matching in combination with (2) \textit{class-based matching}. 
%An unsupervised method complementary to direct matching and semantic matching approaches. 
%It can be applied in combination with the direct matching approaches. 
%specially when the direct matching cannot solve ambiguity in the data due to the lack of overlapping information. 

Given a class of instances from the source dataset, called the \emph{class of interest}, and a set of candidate matches retrieved from the target via direct matching, class-based matching helps to refine the candidates by filtering out those that do not map to the class of interest. 
%method infer the Sameas relations by detecting a class of target instances among those candidates that contains at least one match of each source instance. 
However, it does not assume that the class semantics  is explicitly given so that a direct matching at the class level is possible between the source (e.g.\ Drugs) and target (e.g.\ Medication). Instead, class-based matching uses the idea that the correct matches to the source instances should be similar among themselves, i.e.\ should belong to a class (or share some data attribute / value). Then, by comparing the candidates in a non-trivial way, class-based matching can leverage a class of  target candidates that are more likely to be the positive matches to the source instances. During this process, there is no comparison between source and target but only data from the target is used for matching. 

%Instead, it is a data-driven approach, which derives the class of interest from information in the target. Then, candidates in the target are compared with this latent representation of the class of interest. During this process, there is no comparison between source and target but only data from the target is used for matching. 

For example, the instances \verb+nyt:2223+ and 
\verb+nyt:5962+ from the source dataset \emph{nyt} belong to the class ``cities in California''. The candidates matches from the target dataset \emph{db} are \verb+db:San_Francisco+, \verb+db:Belmont_France+ and \verb+db:Belmont_+ \verb+California+. Employing class-based matching would help to recognize that only \verb+db:Belmont_California+  and \verb+db:San_+ \verb+Francisco+ are correct matches because they belong to a class that corresponds to ``cities in California'', the class of interest.  This matching does not involve any direct comparison between instances in these two datasets. Also, it does not assume the class to which \verb+db:Belmont_California+ and \verb+db:San_+\verb+Francisco+ belong to is explicitly given, so that it can be directly compared with ``cities in California''. Instead, a latent instance-based representation is inferred from the three candidates retrieved from the target in this example. 
%, and then used to refine these candidates. 
%they are the most similar class of instances (they have the same value for \textit{db:country}) among the candidates. Although this is a quite straightforward reasoning, it is effective when the target class of instances can be detected in this fashion.
%

%Besides the main idea behind class-based matching, we also propose (4) optimizations to \emph{compactly represent the class of interest} for greater efficiency and (5) a method to \emph{automatically select the threshold }used for filtering matches. 

We (3) evaluated this approach called SERIMI using data from OAEI 2010 and 2011, two reference benchmarks in the field, and compared the results with OAEI results as well as those obtained from other state-of-the-art systems. These \emph{extensive experiments} show that SERIMI yields superior results. Class-based matching achieved competitive results when compared to the direct matching; most importantly, it was complementary to it; i.e. achieved good performance when direct matching's performance was bad. Thus, using only a simple combination of the two, our approach could greatly improve the results of existing systems. Considering all tasks in OAEI 2010, it increases average F1 result of the second best by 0.21 (from 0.76 to 0.97). For 2011 data, SERIMI also greatly improves the results of recently proposed approaches (\emph{PARIS}~\cite{DBLP:journals/pvldb/SuchanekAS11} and \emph{SIFI-Hill}~\cite{DBLP:journals/pvldb/WangLYF11}). Compared to the best system participated at OAEI 2011, SERIMI achieved the same performance. However, while that system leverages domain knowledge and assumes manually engineered mappings, our approach is generic, completely automatic and does not assume any training data. 
%on any we do not use any domain knowledge, which was exploited by the best baseline to gain accuracy in a few specific tasks evaluated.  

\textbf{Outline.} This paper is organized as follows: In Section 2, we provide an overview of the instance matching process implemented by SERIMI. 
%Section 4 introduces the problem of instance matching over heterogeneous data, where we introduce an entropy based way of finding IFP and Sameas relation on data.
In Section 3, we discuss class-based matching and its optimization. In Section 4, we present a measure of complexity and a detailed analysis of matching tasks based on this measure. This section also contains the results of our experiments, where we compare SERIMI with state-of-the-art approaches. In Section 5, we discuss related works. Finally, we conclude in Section 6. 